
import java.util.*;

/**
 * @author 03010570
 * @date 2020/07/13
 * describe:    LeetCode : 1002 、查找常用字符 https://leetcode-cn.com/problems/find-common-characters/
 */
public class LeetCode_1002 {
    public static void main(String[] args) {
        String[] strings = new String[]{"bella", "label", "roller"};
        List<String> list = commonChars(strings);
        for (String s : list) {
            System.out.print(s + " , ");
        }
        System.out.println();
        String[] strings2 = new String[]{"cool", "lock", "cook"};
        List<String> list2 = commonChars(strings2);
        for (String s : list2) {
            System.out.print(s + " , ");
        }
    }

    /**
     * 将小写字母转换成 数组， char - 'a'  得到小写字母的数组中的下标，数组的值 表示 元素的数量
     * 时间复杂度 ： O(M*N)   数组的长度 * 字符串长度
     * 空间复杂度 ： O(1)     长度为 26 的固定数组
     *
     * @param A
     * @return
     */
    public static List<String> commonChars(String[] A) {
        int[] res = new int[26];
        for (char c : A[0].toCharArray()) {
            res[c - 'a'] += 1;
        }
        for (int i = 0; i < A.length; i++) {
            int[] temp = new int[26];
            for (char c : A[i].toCharArray()) {
                temp[c - 'a'] += 1;
            }
            for (int j = 0; j < 26; j++) {
                if (temp[j] < res[j]) {
                    res[j] = temp[j];
                }
            }
        }
        List<String> list = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            if (res[i] > 0) {
                for (int j = 0; j < res[i]; j++) {
                    list.add((char) (i + 'a') + "");
                }
            }
        }
        return list;
    }


    /**
     * 使用一个 map 记录上一个值的子集，当前字符串 map 跟上一个map子集进行比较，
     * 依次比对到最后一个字符串
     * 时间复杂度 ： O(M*N)  数组的长度 * 字符串的长度
     * 空间复杂度 ： O(N)    字符串的长度
     *
     * @param A
     * @return
     */
    public static List<String> commonChars1(String[] A) {
        if (A.length == 1) {
            return Arrays.asList(A);
        }
        Map<Character, Integer> map = new HashMap<>();
        for (char aChar : A[0].toCharArray()) {
            map.put(aChar, map.getOrDefault(aChar, 0) + 1);
        }
        for (int i = 1; i < A.length; i++) {
            Map<Character, Integer> mapTemp = new HashMap<>(map);
            map.clear();
            for (char aChar : A[i].toCharArray()) {
                if (mapTemp.get(aChar) != null && (map.get(aChar) == null || mapTemp.get(aChar) > map.get(aChar))) {
                    map.put(aChar, map.getOrDefault(aChar, 0) + 1);
                }
            }
        }
        List<String> list = new ArrayList<>();
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            for (int i = 0; i < entry.getValue(); i++) {
                list.add(entry.getKey().toString());
            }
        }
        return list;
    }
}
